package Ex1;

import java.util.*;

/**
 * ADT: Binary Tree.
 */
public interface BinaryTree<E> extends Iterable<E>{

	/**
	 * Returns the count of nodes in the binary tree.
	 */
	public int size();

	/**
	 * Returns whether the tree is empty.
	 */
	public boolean isEmpty();

	/**
	 * Returns an iterator on the binary tree.
	 */
	public Iterator<E> iterator();

	/**
	 * Replaces the element at the position with the specified element,
	 * and returns the replaced element.
	 * Requires: The position is valid.
	 */
	public Object replace(Position<E> p, E e);

	/**
	 * Returns the root of the binary tree.
	 * Requires: The binary tree is not empty.
	 */
	public Position<E> root();

	/**
	 * Returns the father of the position.
	 * Requires: The position is valid and not the root.
	 */
	public Position<E> parent(Position<E> p);

	/**
	 * Returns whether the position is an internal node.
	 * Requires: The position is valid.
	 */
	public boolean isInternal(Position<E> v);

	/**
	 * Returns whether the position is an external node.
	 * Requires: The position is valid.
	 */
	public boolean isExternal(Position<E> v);

	/**
	 * Returns whether the position is the root of the binary tree.
	 * Requires: The position is valid.
	 */
	public boolean isRoot(Position<E> v);

	/**
	 * Adds the element as root and returns the position of this root.
	 * Requires: The binary tree is empty.
	 */
	public Position<E> addRoot(E e);

	/**
	 * Returns the left child of the position.
	 * Requires: The position is valid and has a left child.
	 */
	public Position<E> left(Position<E> v);

	/**
	 * Returns the right child of the position.
	 * Requires: The position is valid and has a right child.
	 */
	public Position<E> right(Position<E> n);

	/**
	 * Returns whether the position has a left child.
	 * Requires: The position is valid.
	 */
	public boolean hasLeft(Position<E> v);

	/**
	 * Returns whether the position has a right child.
	 * Requires: The position is valid.
	 */
	public boolean hasRight(Position<E> v);

	/**
	 * Inserts the element as left child of the position,
	 * and returns the position of the new left child.
	 * Requires: The position is valid and does not have a left child.
	 */
	public Position<E> insertLeft(Position<E> v, E e);

	/**
	 * Inserts the element as right child of the position,
	 * and returns the position of the new right child.
	 * Requires: The position is valid and does not have a right child.
	 */
	public Position<E> insertRight(Position<E> v, E e);

	/**
	 * Removes and returns the element at the position.
	 * Requires: The position is valid and has at most one child.
	 */
	public E remove(Position<E> v);

	/**
	 * Returns the sibling of the position.
	 * Requires: The position is valid and has a sibling.
	 */
	public Position<E> sibling(Position<E> n);

	/**
	 * Adds the trees t1 and t2 as left and right subtree of the position. 
	 * Requires: The position is valid and is an external node.
	 */
	public void attach(Position<E> v, BinaryTree<E> t1, BinaryTree<E> t2);

}
